A navigation mesh, or navmesh, is an abstract data structure used in

artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech r ...

applications to aid agents in

pathfinding Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the sh ...

through complicated spaces. This approach has been known since at least the mid-1980s in

robotics Robotics is an interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrate ...

, where it has been called a meadow map, and was popularized in

video game AI In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-player characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of vid ...

in 2000.

Description

A navigation mesh is a collection of two-dimensional

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...

s (a

polygon mesh In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles ( triangle mesh), quadrilaterals (quads), or other simple convex p ...

) that define which areas of an environment are traversable by agents. In other words, a character in a game could freely walk around within these areas unobstructed by trees, lava, or other barriers that are part of the environment. Adjacent polygons are connected to each other in a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

. Pathfinding within one of these polygons can be done trivially in a straight line because the polygon is convex and traversable. Pathfinding between polygons in the mesh can be done with one of the large number of graph search algorithms, such as A*. Agents on a navmesh can thus avoid computationally expensive

collision detection Collision detection is the computational problem of detecting the intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing fields, primarily in computer grap ...

checks with obstacles that are part of the environment. Representing traversable areas in a 2D-like form simplifies calculations that would otherwise need to be done in the "true" 3D environment, yet unlike a 2D grid it allows traversable areas that overlap above and below at different heights. The polygons of various sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids can.

Creation

Navigation meshes can be created manually, automatically, or by some combination of the two. In video games, a

level designer In video games, a level (also referred to as a map, stage, or round in some older games) is any space available to the player during the course of completion of an objective. Video game levels generally have progressively-increasing difficulty t ...

might manually define the polygons of the navmesh in a

level editor In video games, a level (also referred to as a map, stage, or round in some older games) is any space available to the player during the course of completion of an objective. Video game levels generally have progressively-increasing difficulty t ...

. This approach can be quite labor intensive. Alternatively, an application could be created that takes the level geometry as input and automatically outputs a navmesh. It is commonly assumed that the environment represented by a navmesh is static – it does not change over time – and thus the navmesh can be created

offline In computer technology and telecommunications, online indicates a state of connectivity and offline indicates a disconnected state. In modern terminology, this usually refers to an Internet connection, but (especially when expressed "on line" or ...

and be immutable. However, there has been some investigation of online updating of navmeshes for dynamic environments.

History

In robotics, using linked convex polygons in this manner has been called "meadow mapping", coined in a 1986

technical report A technical report (also scientific report) is a document that describes the process, progress, or results of technical or scientific research or the state of a technical or scientific research problem. It might also include recommendations and c ...

by Ronald C. Arkin. Navigation meshes in video game artificial intelligence are usually credited to Greg Snook's 2000 article "Simplified 3D Movement and Pathfinding Using Navigation Meshes" in ''Game Programming Gems''. In 2001, J.M.P. van Waveren described a similar structure with convex and connected 3D polygons, dubbed the "Area Awareness System", used for

bots The British Overseas Territories (BOTs), also known as the United Kingdom Overseas Territories (UKOTs), are fourteen territories with a constitutional and historical link with the United Kingdom. They are the last remnants of the former Bri ...

in ''

Quake III Arena ''Quake III Arena'' is a 1999 multiplayer-focused first-person shooter developed by id Software. The third installment of the ''Quake'' series, ''Arena'' differs from previous games by excluding a story-based single-player mode and focusing prima ...

''.

Notes

References

* * * * * * *

External links

UDK: Navigation Mesh ReferenceSource Engine: Navigation MeshesCry Engine Navigation And AI
{{DEFAULTSORT:Navigation Mesh Graph data structures Video game development Computational physics Robotics